package 第七周;

/*
 * @author  YxinMiracle
 * @date  2022-05-07 14:52
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.Arrays;

public class 分割等和子集 {

    // 01 背包问题
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[n+1];
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            newNums[i] = nums[i - 1];
            sum += newNums[i];
        }
        if (sum % 2 == 1) return false;

        boolean[] f = new boolean[sum + 1];
        Arrays.fill(f, false);
        f[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = sum; j >= newNums[i] ; j--) {
                f[j] = f[j] | f[j-newNums[i]];
            }
        }

        return f[sum/2];
    }


}
